#include<iostream>
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        Node* now = head;
        while (now != nullptr) {
            Node* newNode = new Node(now->val);
            newNode->next = now->next;
            now->next = newNode;
            now = newNode->next;
        }
  
        now = head;
        while (now != nullptr) {
            Node* nowRandom = now->random;
            if (nowRandom == nullptr) {
                now->next->random = nullptr;
            }
            else {
                now->next->random = nowRandom->next;
            }
            now = now->next->next;
        }
        now =head ;
        Node* res = head->next;
        while (now != nullptr) {
            Node* clone = now->next;
            now->next = clone->next;
            if (now->next == nullptr) return res;
            clone->next = clone->next->next;
            now = now->next;
        }
        return res;
    }
    void getoust(Node* a) {
        while (a != nullptr) {
            std::cout << a->val << ""<<a->random<<"\n";
            a = a->next;
        }
    }
};